package codeRandomThoughts.Test112路径总和;

import codeRandomThoughts.utils.TreeNode;


//路径总和二刷
class Solution3 {
    int pathSum;
    boolean isEqual;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        pathSum = 0;
        isEqual = false;
        if (root == null) return isEqual;
        pathSum += root.val;
        backtracking(root, targetSum);
        return isEqual;
    }

    public void backtracking(TreeNode root, int targetSum) {
        //剪枝
        if (isEqual) return;

        //终止条件
        if (root.left == null && root.right == null) {
            if (pathSum == targetSum) isEqual = true;
            return;
        }

        //单层递归逻辑
        if (root.left != null) {
            pathSum += root.left.val;
            backtracking(root.left, targetSum);
            pathSum -= root.left.val;
        }
        if (root.right != null) {
            pathSum += root.right.val;
            backtracking(root.right, targetSum);
            pathSum -= root.right.val;
        }
    }
}
